#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/22
# @Author   :Changshu
# @File     :practice_155.py
# 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
#
# push(x) —— 将元素 x 推入栈中。
# pop() —— 删除栈顶的元素。
# top() —— 获取栈顶元素。
# getMin() —— 检索栈中的最小元素。

'''不好的做法
class MinStack:
	def __init__(self):
		self.min=10**12
		self.data=[]

	def push(self,x:int)->None:
		self.data.insert(0,x)
		if x<=self.min:
			self.min=x

	def pop(self):
		if len(self.data)<=0:
			return None
		t=self.data.pop(0)
		if len(self.data)>0:
			self.min=min(self.data)
		else:
			self.min=10**12


	def top(self)->int:
		if len(self.data)<=0:
			return None
		return self.data[0]

	def getMin(self)->int:
		if len(self.data)<=0:
			return None
		return self.min
'''


'''使用额外空间来保存最小值'''
import math
class MinStack:
	def __init__(self):
		self.data=[]
		self.minData=[math.inf]
	def push(self,x:int)->None:
		self.data.append(x)
		self.minData.append(min(x,self.minData[-1]))
	def pop(self):
		self.data.pop()
		self.minData.pop()

	def top(self) -> int:
		return self.data[-1]

	def getMin(self) -> int:
		return self.minData[-1]
if __name__ == '__main__':
	# minStack =MinStack()
	# minStack.push(-2)
	# minStack.push(0)
	# minStack.push(-3)
	# print(minStack.getMin())
	# minStack.pop()
	# print(minStack.top())
	# print(minStack.getMin())
	minStack = MinStack()
	minStack.push(2147483646)
	minStack.push(2147483646)
	minStack.push(2147483647)
	print(minStack.top())
	minStack.pop()
	print(minStack.getMin())
	minStack.pop()
	print(minStack.getMin())
	minStack.pop()
	minStack.push(2147483647)
	print(minStack.top())
	print(minStack.getMin())
	minStack.push(-2147483648)
	print(minStack.getMin())
	minStack.pop()
	print(minStack.getMin())
